package tree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.function.Consumer;

/**
 * 表达式计算
 */
public class ExpressCompute {

    public static Integer compute(String exp) {
        //运算符栈
        LinkedList<Character> operatorStack = new LinkedList<>();
        //操作数栈
        LinkedList<Integer> numberStack = new LinkedList<>();

        parse(exp, nextItem -> {
            if (isOperator(nextItem)) {
                char c = (char) nextItem;
                if (')' == c) {
                    doCompute(operatorStack, numberStack);
                } else {
                    operatorStack.addLast(c);
                }
            } else {
                numberStack.addLast((Integer) nextItem);

                //如果栈顶是乘和除，优先级高，优先计算
                if (!operatorStack.isEmpty()) {
                    Character operator = operatorStack.peekLast();
                    if ('*' == operator || '/' == operator) {
                        doCompute(operatorStack, numberStack);
                    }
                }
            }
        });

        //只有一个数才表明计算完毕
        while (numberStack.size() > 1) {
            doCompute(operatorStack, numberStack);
        }
        return numberStack.pollLast();
    }

    /**
     * 触发一次计算(如果有左括号，遇到左括号则停止，否则计算完)
     *
     * @param operatorStack
     * @param numberStack
     */
    private static void doCompute(LinkedList<Character> operatorStack, LinkedList<Integer> numberStack) {
        while (!operatorStack.isEmpty()) {

            Character operator = operatorStack.pollLast();
            if ('(' == operator) {
                continue;
            }

            Integer number2 = numberStack.pollLast();
            Integer number1 = numberStack.pollLast();

            if ('+' == operator) {
                numberStack.addLast(number1 + number2);
            } else if ('-' == operator) {
                numberStack.addLast(number1 - number2);
            } else if ('*' == operator) {
                numberStack.addLast(number1 * number2);
                //乘和除触发的计算没有传递性
                break;
            } else if ('/' == operator) {
                numberStack.addLast(number1 / number2);
                //乘和除触发的计算没有传递性
                break;
            }
        }
    }

    /**
     * 解析下个元素
     *
     * @param exp
     * @return 如果是操作符则返回Character，否则则返回Integer
     */
    private static void parse(String exp, Consumer<Object> itemConsumer) {
        for (int start = 0; start < exp.length(); start++) {
            Character cur = exp.charAt(start);
            if (cur == ' ') {
                continue;
            }

            //遇到运算符号
            if (isOperator(cur)) {
                itemConsumer.accept(cur);
                continue;
            }

            //遇到数字
            StringBuilder number = new StringBuilder(String.valueOf(cur));
            for (start++; start < exp.length(); start++) {
                char next = exp.charAt(start);
                if (next == ' ' || isOperator(next)) {
                    break;
                }
                number.append(next);
            }
            start--;

            itemConsumer.accept(Integer.parseInt(number.toString()));
        }
    }

    /**
     * 判断是否为运算符号
     * @return
     */
    private static boolean isOperator(Object c) {
        List<Character> characters = Arrays.asList('+', '-', '*', '/', '(', ')');
        return characters.contains(c);
    }

    public static void main(String[] args) {
//        System.out.println(compute("1 + ( ( 2 + 3 ) * 4) - 5"));
//        System.out.println(compute("8 * 7 - 666 / 2"));
        System.out.println(compute("(25 - 10 / 2 * 3) / (8 - 3) + 15 * 2 - 3 * 6 / 4"));
    }
}
